#include<bits/stdc++.h>
#define int long long 
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)write(x/10);
	putchar(x%10+'0');	
}
int Dis(int x,int y){if(x==y)return 0;return 1ll*x*y/__gcd(x,y);}
int sol(){
	int a=read(),b=read();
	if(a>b)swap(a,b);
	if(b%a==0)write(b);
	else if(__gcd(a,b)==1){
		int min1=a;
		for(int j=2;j*j<=a;j++)
			if(a%j==0){
				min1=min(min1,j);
			}
		int min2=b;
		for(int j=2;j*j<=b;j++)
			if(b%j==0)min2=min(min2,j);
		write(Dis(min1,a)+Dis(min2,b)+min(Dis(min1,2)+Dis(2,min2),Dis(min1,min2)));
	}else write(a+b);
	putchar('\n');
}
signed main(){
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	int T=read();
	while(T--)sol();
	return 0;
}
